1) Field of the Invention
The present invention relates to a method and apparatus composing a routing processing procedure (algorithm) on the basis of predetermined routing design data (routing problem) to generate a routing program, a method and apparatus composing a placement processing procedure (algorithm) for placing components upon the routing process to generate a placement program, and a method and apparatus for determining a routing path in order to route automatically a routing pattern on a circuit board having a number of component pins.
In fabrication of recent semiconductors (LSIs), multichip modules (MCMs), printed circuit boards or the like, there are demands for high-density packaging and placement, and routing accomplished within a short period of time on the less number of signal layers. With decrease of margin (a degree of freedom) due to a trend toward high-density and high-performance as above, it becomes difficult to solve various routing problems and placement problems with one fixed algorithm. For this, it is now necessary to establish high-performance automatic routing technique and automatic placement technique.
2) Description of the Related Art
In the automatic routing technique, a general-purpose automatic routing program 101 describing a predetermined routing processing procedure complies with routing problems (routing design data) of different sorts of printed circuit boards (or semiconductors such as LSIs or the like) 100A, 100B, . . . , 100Z, as shown in FIG. 33.
Likewise, in the automatic placement technique, a general-purpose automatic placement program 102 describing a predetermined placement processing procedure complies with problems of component placement on difference sorts of printed circuit boards (or semiconductors such as LSIs or the like) 100A, 100B, . . . , 100Z, as shown in FIG. 34.
Line search method or maze method are, for example, well known as general automatic routing means to determine routing paths to route automatically routing patterns on a circuit board having a number of component pins.
In the line search method, if two points to be interconnected with the routing pattern on the printed circuit board 110 are given as a start point (component pin) 111 and an end point (component pin) 112, as shown in FIG. 35, the routing path from the start point 111 to the end point 112 is determined in the following manner.
First, an appropriate direction to approach the end point 112 from the start point 111 is selected on the printed circuit board 110, and the first search line 113 is drawn from the starting point in that direction (rightward in an example shown in FIG. 35).
The first search line 113 cannot reach the end point 112, so the second search line 114 is drawn in an appropriate direction at right angles to the first search line 113 to approach the end point 112 (downward in the example shown in FIG. 35).
The second search line 114 cannot reach the end point 112 either because of a routing prohibited region (a part indicated by X marks in FIG. 35), so the third search line 115 at right angles to the second search line 114, the fourth search line 116 at right angles to the third search line 115, the fifth search line 117 at right angles to the fourth search line 116 are successively drawn from appropriate points on immediately above lines, in the same manner. Finally, the fifth search line 117 reaches the end point 112.
The first to fifth search lines 113-117 drawn in the above manner determine a routing path (indicated by a dot-dash line) 118 of a desired routing pattern from the start point 111 to the end point 112 on the printed circuit board 110.
On the other hand, in the maze method, if two points to be routed of a routing pattern are given as a start point (component pin) 121 and an end point (component pin) 122 on a printed circuit board 120 as shown in FIG. 36, a routing path from the start point 121 to the end point 122 is determined in the following manner.
In the maze method, meshes each having a pattern width of the routing pattern as a basic unit are imagined on the printed circuit board 120, and a wave is generated and propagated from the start point 121 toward the end point 122, as shown in FIG. 36.
As shown as an encircled number in each mesh in FIG. 36, meshes adjacent to a mesh in which the start number 121 locates are labelled (1), and the meshes adjacent to the meshes labelled (1) are labelled 2. In the same manner, the numbers are successively labelled to the meshes so that the routing path started from the start point 121 can reach the end point 122.
In an example shown in FIG. 36, a mesh in which the end point 122 locates is the eighth mesh counted from the start point 121, labelled a number (8). The meshes that the wave has passed through from the start point 121 to the end point 122 are successively stored. when the wave reaches the end point 122, the positions of the meshes that the wave has passed through are traced back to the start point 121 from the end point 122 so that the routing path 123 of the routing pattern is determined.
Incidentally, meshes labelled X marks represent a routing prohibited region in FIG. 36.
However, physical, electric design conditions become more strict due to trends to high-density packaging, low-cost and high-speed developed rapidly in recent years. For this, it becomes difficult to find out an appropriate solution as expected by the designer if automatic routing is carried out for a long time, which results in a lot of parts left unrouted.
The automatic routing technique using the general-purpose automatic routing program 101 as shown in FIG. 33 has a problem that the program 101 for solving problems describes only a certain limited routing processing procedure (algorithm) so that it is difficult to find out an optimum solution for each routing problem, although there are various routing problem (routing design data).
As above, the present situation is that it is hard to outlook the completion of the routing process within a given period of time even if manual routing is carried out on unrouted parts, so all parts are manually routed after all. As this, an application rate of the automatic routing is decreasing year after year.
Similarly, in the automatic placement technique using the general-purpose automatic placement program 102 as shown in FIG. 34, the program 102 for solving problems describes only a given limited routing processing procedure (algorithm) although recent substrates are diversified as noted above. For this, the present situation is that the component placement often results in against designer's expectations.
Therefore, the component placement resulted in against designer's expectation requires manual alteration. However, the present situation is that it is hard to outlook the completion of the routing process within a given period of time even if manual alteration is done in the component placement, so all the component placement has to be carried out manually. As this, an application rate of the automatic placement is decreasing year after year.
On the other hand, in the above-mentioned line search method shown in FIG. 35, the routing pattern is represented as succession of straight lines (see the search lines 113-117 and the routing path 118). When a judgement is made as to whether the pattern is passable or not, graphic operations are necessary to judge the positional relation of the straight lines, which graphic operations consume an enormous period of time. With this reason, sufficient search of the routing paths in the routing pattern has been difficult.
In the above-mentioned maze method shown in FIG. 36, since the pattern width is designated as a basic unit of the mesh, so a volume of the data become enormous as an area of the printed circuit plate 120 increases and the width of the pattern decreases. This causes an increase in the number of meshes used to search a passable route. This results in an enormous period of time to search a path.
Therefore, searches to determine a passable path have to be made on many paths and many combinations in order to route the routing pattern in the high-density. However, search at an unsufficient speed causes occurence of paths that have been left unsearched, which disturbs a high-density routing.